//
//  P1757.cpp
//  Algorithm
//
//  Created by 刘锦程 on 2023/9/16.
//

#include <stdio.h>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
struct node{
    int w;
    int v;
    node(int a,int b){
        w=a;
        v=b;
    }
    node(){}
};
int num[101];
node zu[101][101];
int dp[1003];
int P1757ans(){
    cin>>m>>n;
    node a(0,0);
    for(int i=1;i<=n;i++){
        int zuf=0,ww,vv;
        cin>>ww>>vv>>zuf;
        num[zuf]++;
        a=node(ww,vv);
        zu[zuf][num[zuf]]=a;
    }
    for(int k=1;k<=100;k++)
        if(num[k])
            for(int j=m;j>=0;j--){
                for(int i=1;i<=num[k];i++)
                {
                    if(j>=zu[k][i].w)
                    dp[j]=max(dp[j],dp[j-zu[k][i].w]+zu[k][i].v);
                }
            }
   cout<<dp[m]<<endl;
    return 0;
}
